Bug [A]

Memory limit: 64 MB

Your electronic calendar contains an error - something that programmers call a bug. Due to this bug, even integers cannot be entered into the calendar.

You are planning a business trip from Bytetown to Bitcity. Obviously, you would like to take the shortest path for the trip. After you return, you will have to enter the length of the path to your calendar, so the length needs to be an odd integer.

Taking into consideration that the bug in the calendar will surely remain uncorrected for quite a long time, and that the road system in Byteland will probably be reconstructed multiple times, you decided to write a program that will help you in dealing with similar problems in future.

Task

Write a program that:

• reads a description of the map of Byteland from the standard input,
• computes the length of the shortest odd-length path from Bytetown to Bitcity or checks that such path does not exist,
• writes the result to the standard output.

Input

The first line of input contains two integers and (, ), separated by a single space and denoting the number of cities and the number of roads in Byteland. The cities are numbered from to ; Bytetown has number , whereas Bitcity - number .

The following lines describe the system of roads in Byteland. Each of them contains three space-separated integers , , (, , ) denoting a bidirectional road of length connecting cities with numbers and .

Output

The first and only line of output should contain one integer - the length of the shortest odd-length path from Bytetown to Bitcity. The computed path may visit some cities and roads multiple times. Changes in direction of driving (including turning back) can only be performed in cities. If no such path exists, the correct output is .

Example

For the input data:

6 7
1 2 1
2 6 1
1 3 1
5 6 1
3 5 2
3 4 1
5 4 4

the correct result is:

7

Task author: Marcin Pilipczuk.